/**
 *
 * @author     mole<mole1230@gmail.com>
 * @version    $Id: sort.c 91 2011-02-24 06:24:51Z mole1230 $
 */

#include <stdio.h>

/**
 * 选择排序
 *
 * 算法思想简单描述：
 *   在要排序的一组数中，选出最小的一个数与第一个位置的数交换；
 *   然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环
 *   到倒数第二个数和最后一个数比较为止。 
 *
 *   选择排序是不稳定的。算法复杂度O(n2)--[n的平方]
 */
void select_sort(int *x, int n)
{
	int i, j, min, t;

	for (i = 0; i < n; i++) {
		min = i;
		
		for (j = i + 1; j < n; j++) {
			if (*(x + j) < *(x + min)) {
				min = j;
			}
		}

		if (min != i) {
			t = *(x + i);
			*(x + i) = *(x + min);
			*(x + min) = t;
		}
	}
}

/**
 * 插入排序
 *
 * 算法思想简单描述：
 *
 *   在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排
 *   好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
 *   也是排好顺序的。如此反复循环，直到全部排好顺序。
 *     
 *   直接插入排序是稳定的。算法时间复杂度O(n2)--[n的平方]
 */
void insert_sort(int *x, int n)
{
	int i, j, t;

	for (i = 1; i < n; i++) {
		t = *(x + i);
		for (j = i - 1; j >= 0 && t < *(x + j); j--) {
			*(x + j + 1) = *(x + j);
		}

		*(x + j + 1) = t;
	}
}

/**
 * 冒泡算法
 *
 * 算法思想简单描述：
 *
 *   在要排序的一组数中，对当前还未排好序的范围内的全部数，自上
 *   而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较
 *   小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要
 *   求相反时，就将它们互换。
 *      
 *   下面是一种改进的冒泡算法，它记录了每一遍扫描后最后下沉数的
 *   位置k，这样可以减少外层循环扫描的次数。
 *
 *   冒泡排序是稳定的。算法时间复杂度O(n2)--[n的平方]
 */
void bubble_sort(int *x, int n)
{
	int i, j, t, k;

	for (i = n - 1; i > 0; i = k) {
		for (j = 0, k = 0; j < i; j++) {
			if (*(x + j) > *(x + j + 1)) {
				t = *(x + j);
				*(x + j) = *(x + j + 1);
				*(x + j + 1) = t;
				k = j;
			}
		}
	}
}

/**
 * 算法思想简单描述：
 *  
 *   在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，
 *   并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为
 *   增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除
 *   多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现
 *   了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中
 *   记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量
 *   对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成
 *   一组，排序完成。
 *           
 *   下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量，
 *   以后每次减半，直到增量为1。
 *
 *   希尔排序是不稳定的。
 */
void shell_sort(int *x, int n)
{
	int h, j, k, t;

	for (h = n / 2; h > 0; h = h / 2) {
		for (j = h; j < n; j++) {
			t = *(x + j);
			for (k = j - h; k >= 0 && t < *(x+k); k -= h) {
				*(x + k + h) = *(x + k);
			}
			*(x + k + h) = t;
		}
	}
}

static void _quick_sort(int *x, int l, int r)
{
	int i, j, t;

	if (l >= r) {
		return;
	}

	i = l;
	j = r;
	t = x[l];

	while (i != j) {
		while (x[j] >= t && j > i) {
			j--;	
		}

		if (j > i) {
			x[i++] = x[j];
			// x[i] = x[j];
			// i++;
		}

		while (x[i] <= t && j > i) {
			i++;
		}

		if (j > i) {
			x[j--] = x[i];
			// x[j] = x[i];
			// j--;
		}
	}
	x[i] = t;

	_quick_sort(x, l, i - 1);
	_quick_sort(x, i + 1, r);
}

/**
 * 快速排序是对冒泡排序的一种改进。它的基本思想是：
 *
 * 通过一躺排序将要排序的数据分割成独立的两部分，
 * 其中一部分的所有数据都比另外一不部分的所有数据都要小，
 * 然后再按次方法对这两部分数据分别进行快速排序，
 * 整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 */
void quick_sort(int *x, int n)
{
	_quick_sort(x, 0, n - 1);
}

void xprintf(int *x, int n, int end)
{
	int i;
	if (end) {
		printf("end sorting:\n");
	} else {
		printf("before sorting:\n");
	}

	for (i = 0; i < n; i++) {
		printf("%d ", *(x + i));
	}

	printf("\n");
	if (end) {
		printf("-------------------------------------------\n");
	}
}

#define N 10
int main(int argc, char **argv)
{
	int x[N] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
	
//	xprintf(x, N, 0);
//	select_sort(x, N);
//	xprintf(x, N, 1);


//	xprintf(x, N, 0);
//	insert_sort(x, N);
//	xprintf(x, N, 1);


//	xprintf(x, N, 0);
//	bubble_sort(x, N);
//	xprintf(x, N, 1);


//	xprintf(x, N, 0);
//	shell_sort(x, N);
//	xprintf(x, N, 1);


	xprintf(x, N, 0);
	quick_sort(x, N);
	xprintf(x, N, 1);
}

